# 从中序与后序遍历序列，构造二叉树： https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/submissions/

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 递归写法
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        """
            递归
            1. 后序遍历确定根节点， 2. 中序遍历确定根节点的左右子树
        """
        def myBuildTree(in_left, in_right, pos_left, pos_right):
            # 4. 终止条件， 当in_left == in_right 时， 说明只有一个节点了， 再次继续， in_left 必然大于 in_right, 递归结束，返回None
            if in_left > in_right: return None

            # 1. 创建根节点
            node = TreeNode(postorder[pos_right])
            # 2. 找到根节点在 中序数组中的位置
            in_root_index = inorderMap.get(postorder[pos_right])
            # 3. 左右： 要确定其对应的中序，后序 数组的范围
            node.left = myBuildTree(in_left, in_root_index - 1, pos_left, pos_left + in_root_index - in_left - 1)
            node.right = myBuildTree(in_root_index + 1, in_right, pos_left + in_root_index - in_left, pos_right - 1)

            return node
            
        
        # 1. 构建中序的map，定位根节点位置
        inorderMap = {elm: i for i, elm in enumerate(inorder)}
        print(inorderMap)
        # 2. 调用函数
        return myBuildTree(0, len(inorder) - 1, 0, len(postorder) - 1)


# 官方解法，是对这个过程理解的更透彻呀~ ，直接只需要维护 in_left, in_right 即可，代码又简洁不少
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        def helper(in_left, in_right):
            # 如果这里没有节点构造二叉树了，就结束
            if in_left > in_right:
                return None
            
            # 选择 post_idx 位置的元素作为当前子树根节点
            val = postorder.pop()
            root = TreeNode(val)

            # 根据 root 所在位置分成左右两棵子树
            index = idx_map[val]
 
            # 构造右子树
            root.right = helper(index + 1, in_right)
            # 构造左子树
            root.left = helper(in_left, index - 1)
            return root
        
        # 建立（元素，下标）键值对的哈希表
        idx_map = {val:idx for idx, val in enumerate(inorder)} 
        return helper(0, len(inorder) - 1)

        